﻿// Nightmare Ⅱ HDU - 3085.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*
https://vjudge.net/problem/HDU-3085

昨晚，小二月做了一个可怕的噩梦。他梦见他和他的女朋友被困在一个大迷宫里。更可怕的是，迷宫里有两个鬼魂。它们会杀人。现在小二月想知道他是否能在鬼魂找到他们之前找到他的女朋友。
你可以假设小二月和他的女朋友可以向四个方向移动。每秒钟，小二月可以移动3步，他的女朋友可以移动1步。鬼魂很邪恶，它们每秒钟会分裂成几部分，占据距离它们2步以内的格子，直到占据整个迷宫。你可以假设在每一秒钟，鬼魂首先分裂，然后小二月和他的女朋友开始移动，如果小二月或者他的女朋友到达一个有鬼魂的格子，他们就会死去。
注意：新的鬼魂也可以像原来的鬼魂一样分裂。
输入
输入以一个整数T开始，表示测试用例的数量。
每个测试用例以包含两个整数n和m的行开始，表示迷宫的大小。(1<n, m<800)
接下来的n行描述了迷宫。每行包含m个字符。字符可能是：
‘.’ 表示一个空地，所有人都可以走。
‘X’ 表示一堵墙，只有人不能走。
‘M’ 表示小二月
‘G’ 表示女朋友。
‘Z’ 表示鬼魂。
保证迷宫中恰好包含一个字母M，一个字母G和两个字母Z。
输出
在一行中输出一个整数S，表示小二月和他的女朋友将在最短时间S内相遇，如果他们成功相遇，则输出-1表示他们未能相遇。

3
5 6
XXXXXX
XZ..ZX
XXXXXX
M.G...
......
5 6
XXXXXX
XZZ..X
XXXXXX
M.....
..G...

10 10
..........
..X.......
..M.X...X.
X.........
.X..X.X.X.
.........X
..XX....X.
X....G...X
...ZX.X...
...Z..X..X


1
1
-1


*/
int main()
{
    std::cout << "Hello World!\n";
}

 